from typing import *
from cmath import inf


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:

        state = 0
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    state |= 1 << (i * 3 + j)
        ans = inf

        def dis(a, b):
            x, y = a // 3, a % 3
            m, n = b // 3, b % 3
            return abs(m - x) + abs(n - y)

        def f(id, state, tot, k):
            if state == 0:
                nonlocal ans
                ans = min(ans, tot)
                return
            x, y = id // 3, id % 3
            if grid[x][y] == 1 or grid[x][y] == 0:
                f(id + 1, state, tot, 0)
            else:
                grid[x][y] -= 1
                for i in range(k, 9):
                    if (state >> i) & 1 == 1:
                        f(id, state ^ (1 << i), tot + dis(id, i), k + 1)
                grid[x][y] += 1

        f(0, state, 0, 0)
        return ans


s = Solution()
print(s.minimumMoves([[1, 3, 0], [1, 0, 0], [1, 0, 3]]))
